package LRU;

import java.util.HashMap;
import java.util.Map;

/**
 * LRU缓存实现：双向链表 + 哈希表（方案A）
 * 时间复杂度：get/put均为O(1)
 * @param <K> 键类型
 * @param <V> 值类型
 */
public class LRUWithDoubleLinkedList<K, V> {
    // 缓存容量
    private int capacity;
    // 当前缓存数据量
    private int size;
    // 双向链表：头节点（最近访问）、尾节点（最少访问）
    private DoubleLinkedNode<K, V> head, tail;
    // 哈希表：key -> 双向链表节点（O(1)定位）
    private Map<K, DoubleLinkedNode<K, V>> cacheMap;

    // 初始化缓存
    public void init(int capacity) {
        if (capacity <= 0) {
            throw new IllegalArgumentException("缓存容量必须大于0");
        }
        this.capacity = capacity;
        this.size = 0;
        // 初始化头节点和尾节点（哨兵节点，避免边界判断）
        this.head = new DoubleLinkedNode<>();
        this.tail = new DoubleLinkedNode<>();
        head.setNext(tail);
        tail.setPrev(head);
        this.cacheMap = new HashMap<>(capacity);
    }

    /**
     * 根据key查询value
     * @param key 键
     * @return 存在则返回value，否则返回null
     */
    public V get(K key) {
        if (key == null) {
            throw new NullPointerException("key不能为null");
        }
        // 1. 哈希表定位节点
        DoubleLinkedNode<K, V> node = cacheMap.get(key);
        if (node == null) {
            return null;
        }
        // 2. 将节点移至头部（更新访问顺序）
        moveToHead(node);
        return node.getValue();
    }

    /**
     * 插入或更新键值对
     * @param key 键
     * @param value 值
     */
    public void put(K key, V value) {
        if (key == null || value == null) {
            throw new NullPointerException("key或value不能为null");
        }
        // 1. 检查key是否已存在
        DoubleLinkedNode<K, V> node = cacheMap.get(key);
        if (node != null) {
            // 1.1 存在：更新value并移至头部
            node.setValue(value);
            moveToHead(node);
            return;
        }
        // 2. 不存在：新建节点
        DoubleLinkedNode<K, V> newNode = new DoubleLinkedNode<>(key, value);
        // 2.1 插入哈希表
        cacheMap.put(key, newNode);
        // 2.2 插入链表头部
        addToHead(newNode);
        size++;
        // 2.3 若缓存满，淘汰尾部节点
        if (size > capacity) {
            DoubleLinkedNode<K, V> removedNode = removeTail();
            // 从哈希表中移除
            cacheMap.remove(removedNode.getKey());
            size--;
        }
    }

    // -------------------------- 双向链表辅助方法 --------------------------
    /**
     * 将节点添加到链表头部（最近访问位置）
     */
    private void addToHead(DoubleLinkedNode<K, V> node) {
        // 节点的prev指向头节点，next指向头节点的原next
        node.setPrev(head);
        node.setNext(head.getNext());
        // 头节点的原next的prev指向当前节点
        head.getNext().setPrev(node);
        // 头节点的next指向当前节点
        head.setNext(node);
    }

    /**
     * 移除指定节点
     */
    private void removeNode(DoubleLinkedNode<K, V> node) {
        // 前驱节点的next指向当前节点的next
        node.getPrev().setNext(node.getNext());
        // 后继节点的prev指向当前节点的prev
        node.getNext().setPrev(node.getPrev());
    }

    /**
     * 将节点移至头部（先移除再添加）
     */
    private void moveToHead(DoubleLinkedNode<K, V> node) {
        removeNode(node);
        addToHead(node);
    }

    /**
     * 移除尾部节点（最少访问位置，淘汰）
     */
    private DoubleLinkedNode<K, V> removeTail() {
        // 尾部节点是tail的prev
        DoubleLinkedNode<K, V> removedNode = tail.getPrev();
        removeNode(removedNode);
        return removedNode;
    }

    // -------------------------- 状态查询方法 --------------------------
    public int size() {
        return size;
    }

    public boolean isFull() {
        return size == capacity;
    }
}